1. Field of the Invention
The present invention relates to routing packets in a telecommunications network, and, more particularly, to determining paths through nodes of the network for dynamic backup routing of packets for restoration.
2. Description of the Related Art
In interconnected packet networks, such as the Internet, users establish a connection between a source and a destination with a stream of data packets (called a “packet flow” or “flow”) transferred through the network over a network path. The network path is defined by a set of nodes interconnected by a set of links through which packets of the connection are transferred. Packet networks may have a hierarchical structure in which smaller networks are interconnected by larger networks, and a peer structure in which equivalent networks are interconnected. A packet network connects to one or more other packet networks through ingress and egress points (routers) of the network.
Interior routing protocols are employed by network routers to determine a path through the nodes of the network along which packets between a source (ingress) and destination (egress) pair are forwarded. Packets received by a node's router are forwarded to other nodes based on a forwarding table constructed in accordance with the interior routing protocol, but may also be through routes installed with explicit route provisioning. Interior routing protocols may also specify network topology, link capacity/usage, and link-state information (“network information”) that is exchanged between the network nodes. Network information allows the node's router to construct the corresponding forwarding table. An example of a widely used interior routing protocol for “best-effort” routing is the Open Shortest Path First (OSPF) protocol. In addition, some routing protocols associate a link “cost” with each link between nodes. This link cost may be associated with, for example, average link utilization or revenue generated by the link, as well as link “importance” in the network (i.e., how critical the link is to packet routing). When link-state information or link-bandwidth information (e.g., connectivity or available bandwidth) is exchanged between routers, each router in the network has a complete description of the network's topology.
Routing protocols, in addition to providing connectivity, may also enable traffic management. The Multi-Protocol Label Switched (MPLS) standard, for example, allows such routing protocols for traffic management. The MPLS standard may be employed for networks having virtual circuits (packet flows) or label switched paths (LSPs) with provisioned service levels (also known as guaranteed quality-of-service (QoS) levels).
Provisioned service levels may be, for example, a guaranteed minimum bandwidth for the path of a packet flow through the network. This path having a guaranteed level of service between ingress and egress points may be referred to as a Network Tunnel Path (NTP). As would be apparent to one skilled in the art, specific implementations of NTPs exist for different types of networks. As examples of NTPs, virtual circuits may be established for packet flows in TCP/IP networks, virtual circuits may be established for cells in Asynchronous Transfer Mode (ATM) networks, and label switched paths (LSPs) may be established for packets in MPLS networks. Packets of a signaling protocol, such as RSVP (Reservation Protocol for IP and MPLS networks) with traffic engineering extensions or CR-LDP (Constrained Routing Label Distribution Protocol for MPLS networks), may be used to reserve link bandwidth and establish an NTP. NTPs may be provisioned as explicit routes along specific paths between nodes of the network (i.e., when an NTP is provisioned, all intermediate points may be specified through which a packet passes between the ingress and egress points of the NTP).
In MPLS networks, packets are encapsulated by appending to the packet, or forming from the packet, additional information when the packet is received at an ingress point. The additional information, sometimes referred to as a label, is then employed by routers of the network to forward the corresponding packet. In some cases, the label may simply be a pointer that identifies or is otherwise related to specific origination and termination address fields in the header of the received packet.
Of increasing importance to network designers is to design networks with NTPs having guaranteed levels of service that incorporate restoration mechanisms, such as MPLS restoration for LSPs. These restoration mechanisms allow for provisioning of, and/or capacity reservation for, backup paths through the network onto which traffic of affected NTPs may be redirected relatively quickly upon detection of an element/link failure within the network. Often, the restoration path is provisioned concurrently when the original NTP of a request arriving at the network is provisioned.
Prior art methods to provide backup for network element/link failures usually determine two link-disjoint paths between the source and the destination of the demands, and then use one for the primary and one for the secondary. This prior art method is sometimes referred to as end-to-end restoration In end-to-end restoration, the secondary (backup) path is link (and/or node) disjoint from the primary (active) path. Link disjoint means that the primary and secondary paths do not have any links in common. Node disjoint means that the primary and secondary paths do not have any nodes in common, with the exception of the source and destination nodes.
FIG. 1 shows a network 100 having primary path 101 and secondary path 102 for a connection having end-to-end restoration between source node s (node 111) and destination node t (node 115). Primary path 101 (shown with solid link arrows) passes from node 111 through nodes 112, 113, and 114 to the destination node 115. Secondary path 102 (shown with dashed link arrows) passes from node 111 through nodes 116, 117, and 118 to the destination node 115. FIG. 2 shows the network 100 of FIG. 1 in which a failure between nodes 113 and 114 occurs. FIG. 2 shows the direction of information transfer from node 113 through node 112 to the source s (node 111) to detect the failure for the paths illustrated in FIG. 1. The information transferred is simply that the link has failed. The information is transferred back to the source, which then switches to the backup secondary path 102.
However, this approach in end-to-end restoration may have an unnecessarily long delay before switching from the primary to secondary path. This delay may occur because information has to propagate back to the source, which in turn switches from the primary to the secondary path for all the demands that use the link.